package leetcode.f1t100;

/**
 * 求两个有序数列的中位数, 数量为偶数则取两个中位数求平均值
 *
 * https://leetcode.com/problems/median-of-two-sorted-arrays/
 *
 * @author lichx
 * @date 2021/9/15 10:51
 */
public class Q4_MedianOfTwoSortedArray {
    public static void main(String[] args) {
        int[] nums1 = new int[]{1};
        int[] nums2 = new int[]{};
        System.out.println(findMedianSortedArrays1(nums1, nums2));
        System.out.println(findMedianSortedArrays(nums1, nums2));
    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int middown = ((len1 + len2 + 1) >> 1);
        int up = -1;
        int i = -1, j = -1;
        for (int k = 0; k < middown; k++) {
            if(i+1 == len1){
                up=nums2[++j];
            }else if(j+1  == len2){
                up = nums1[++i];
            }else if(nums1[i+1] < nums2[j+1]){
                up = nums1[++i];
            }else{
                up=nums2[++j];
            }
        }
        boolean isOdd = (len1 + len2)%2==1;
        if (isOdd) {
            return up;
        }

        int down = 0;
        if(i == len1-1){
            down = nums2[j+1];
        }else if(j==len2-1){
            down = nums1[i+1];
        }else{
            down = Math.min(nums1[i+1],nums2[j+1]);
        }
        return (up + down) / 2.0;
    }

    public static double findMedianSortedArrays1(int[] A, int[] B) {
        //make A the shorter of the 2 arrays, less looping time
        if (A.length > B.length) {
            int[] temp = A;
            A = B;
            B = temp;
        }

        int sizeA = A.length;
        int sizeB = B.length;
        int totalSize = sizeA + sizeB;

        //calculate how many numbers there are to the left of the final result,
        //this number includes the median if total size is odd, including half of the median if total size is even
        //i e: if total size is 11; then (11 + 1) / 2 = 6, which means the 6th number in order is the median
        //     if total size is 10, then (10 + 1) / 2 = 5, which means the 5th number in order is half of the median
        //        and we need to find the other half.
        int count = (totalSize + 1)/2;


        //we do binary search on array A, trying to see how many numbers in Array A is in "count"
        //we do not need to do binary search on array B, because we know the "count", so the numbers to keep in array B
        //   is just count - numberToKeepIn1
        int start = 0;
        int end = sizeA;
        while (start <= end) {
            //find the number of digits to keep in array A, these are the numbers we are still considering
            // note: this is the # of digits, not index, ie: the 5th digit is at index 4
            int numberToKeepIn1 = start + (end - start) / 2;

            //find the number of digits to keep in array B, these are the numbers we are still considering
            int numberToKeepIn2 = count - numberToKeepIn1;


            // we are still considering some number in array A, but the last digit we are considering in array A is bigger than the
            // next digit in array B
            if(numberToKeepIn1 > 0 && A[numberToKeepIn1 - 1] > B[numberToKeepIn2]) {
                end = numberToKeepIn1 - 1;
            }

            // we are still considering some number in array A, but the last digit we are considering in array B is bigger than the
            // next digit in array A
            else if(numberToKeepIn1 < sizeA && B[numberToKeepIn2 - 1] > A[numberToKeepIn1]) {
                start = numberToKeepIn1 + 1;
            }

            // we have all the numbers we want, and the median is the biggest number in here
            else {
                int result;
                if(numberToKeepIn1 == 0) { //no longer considering any number in Array A, then the median is just the median of the array B array
                    result = B[numberToKeepIn2 - 1];
                } else if(numberToKeepIn2 == 0){ //no longer considering any number in Array B, then the median is just the median of array A array
                    result = A[numberToKeepIn1 - 1];
                } else { //take some from array A, take some from the array B, the median is the largest of the two numbers we are still considering in the two arrays
                    result = Math.max(A[numberToKeepIn1 - 1], B[numberToKeepIn2 - 1]);
                }

                // if is total size is odd, we done
                if ((totalSize & 1) == 1) {
                    return result;
                }

                //is even, we need to find the other half and take the average of the two numbers
                int nextValue;
                if(numberToKeepIn1 == sizeA) { //if all numbers in Array A are taken
                    nextValue = B[numberToKeepIn2];
                } else if(numberToKeepIn2 == sizeB) { //if all numbers in Array B are taken
                    nextValue = A[numberToKeepIn1];
                } else {                                //take the min of the two candidates
                    nextValue = Math.min(B[numberToKeepIn2], A[numberToKeepIn1]);
                }

                return (result + nextValue) / 2.0;
            }
        }

        return 0.0; //never reaches here
    }
}
